package cn.hycat.leetcode.middle;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @author 吕泽浩业
 * @version 1.0
 */
/*给定一个长度为n的链表head

        对于列表中的每个节点，查找下一个 更大节点 的值。
        也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。
        返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。
        如果第 i 个节点没有下一个更大的节点，设置answer[i] = 0。*/

public class L1019链表中的下一个更大节点 {
      public class ListNode {
          int val;
          ListNode next;

          ListNode() {
          }

          ListNode(int val) {
              this.val = val;
          }

          ListNode(int val, ListNode next) {
              this.val = val;
              this.next = next;
          }
      }

    public int[] nextLargerNodes(ListNode head) {
        ArrayList<Integer> list = new ArrayList();
        ListNode listNode = head;
        while(listNode != null) {
            list.add(listNode.val);
            listNode = listNode.next;
        }

        int[] ans = new int[list.size()];

        Stack<Integer> s = new Stack();
        for(int i = 0; i < list.size(); i++) {
            while(!s.isEmpty() && list.get(i) > list.get(s.peek())) {
                ans[s.peek()] = list.get(i);
                s.pop();
            }
            s.push(i);
        }
        return ans;
    }
}
